package done.easy_501_600;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static java.lang.Math.abs;

/**
 * 563. Binary Tree Tilt 二叉树的坡度
 * <p>
 * 给定一个二叉树，计算整个树的坡度。
 * 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子
 * 树结点之和的差的绝对值。空结点的的坡度是0。
 * 整个树的坡度就是其所有节点的坡度之和。
 * <p>
 * 示例:
 * 输入:
 * <p>
 * 1
 * /   \
 * 2     3
 * <p>
 * 输出: 1
 * 解释:
 * 结点的坡度 2 : 0
 * 结点的坡度 3 : 0
 * 结点的坡度 1 : |2-3| = 1
 * 树的坡度 : 0 + 0 + 1 = 1
 *
 * @author 大硕
 * 2019-03-30 6:56 PM
 **/
@Slf4j
public class BinaryTreeTilt {

    int result = 0;

    @SuppressWarnings("all")
    public int findTilt(TreeNode root) {
        // 190330 first
        // 190408 second 用了两次解决
        return -1;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1, 2, 3);
        log.info("{}", findTilt(root));
    }
}





























/*
int tilt = 0;

public int findTilt(TreeNode root) {
    posOrder(root, tilt);
    return tilt;
}

private int posOrder(TreeNode root) {
    if (root == null) {
        return 0;
    }

    // 左子树的总和
    int left = posOrder(root.left);

    // 右子树的总和
    int right = posOrder(root.right);

    // 审题：整个树的坡度就是其所有节点的坡度之和。
    tilt += abs(left - right);

    // 左右子树的总和, 用来给上一级计算坡度用
    return left + right + root.val;
}
*/
